import java.util.PriorityQueue;

class MedianFinder {
    // 创建两个堆
    // 大根堆
    PriorityQueue<Integer> queueMax;
    // 小根堆
    PriorityQueue<Integer> queueMin;

    public MedianFinder() {
        // 初始化大小根堆
        queueMax = new PriorityQueue<>((a, b) -> b - a);
        queueMin = new PriorityQueue<>((a, b) -> a - b);
    }

    public void addNum(int num) {
        // 进行分类讨论
        // 如果两个堆里面数量一样
        if (queueMax.size() == queueMin.size()) {
            if (queueMax.isEmpty() || num <= queueMax.peek()) {
                // 进入大根堆
                queueMax.offer(num);
            } else {
                // 进入小根堆
                queueMin.offer(num);
                // 这时小根堆的堆顶元素出堆 放入大根堆
                queueMax.offer(queueMin.poll());
            }
        } else{
            if (num <= queueMax.peek()) {
                // 进入大根堆
                queueMax.offer(num);
                // 大根堆堆顶元素出堆进入小根堆
                queueMin.offer(queueMax.poll());
            } else {
                // 直接进入小根堆
                queueMin.offer(num);
            }
        }
    }

    public double findMedian() {
        if (queueMax.size() > queueMin.size()) {
            return queueMax.peek();
        }
        return (queueMin.peek() * 1.0 + queueMax.peek() * 1.0) / 2;
    }
}
